Ant colony optimization is concerned with the development and use of optimization algorithms inspired by the collective behaviour of large colonies of social insects. Typically, the algorithms represent a problem space as a network of nodes connected by arcs. The network is traversed by simple, autonomous agents that are capable both of depositing virtual markers on nodes and arcs, and acting upon the accumulated markers that they encounter on their travels. By an appropriate choice of agent behaviours, some emergent characteristic of the network can be caused to converge on a (near-)optimal solution to the original problem. This approach has been successfully applied to a range of problems such as the ‘Traveling Salesman’ Problem and job scheduling. More detailed information about the approach can be found in Swarm Intelligence by Bonabeau, Dorigo & Teraulaz (Oxford University Press, 1999).
Artificial life seeks to understand the processes by which biological and social complexity arise from simple organisms or agents. Typically, the approach is to construct a computer simulation of a universe populated by such agents and to study their interaction and evolution. The simulated universes may or may not reflect natural laws, and the agents may or may not be modeled on naturally occurring organisms. Within that context, the simulation of ant-like agents with the capability to deposit and sense virtual markers (pheromones) has been known for at least a decade (for example, see Ant Farm: Towards Simulated Evolution by Collins & Jefferson (in Artificial Life II, Farmer et al, Addison Wesley, 1991).
Agent-based robotics applies similar ideas to motivate the development and exploration of swarms of simple interacting robots operating in the real world. The idea of pheromone deposition and detection is well known in this field but is primarily used metaphorically to inspire mechanisms that actually implement direct communication between individuals rather than indirect communication through the environment in which the individuals move. For example, see Progress in Pheromone Robotics by Payton, Estkowski & Howard (preprint, 7th International Conference on Intelligent Autonomous Systems, Mar. 25-27, 2002). An exception is the work of Andrew Russell in which robots do deposit (and sense) a chemical marker directly into the environment (see http://www.ecse.monash.edu.au/staff/rar/).
It is an object of a first aspect of the present invention to use the concept of pheromones to provide trail information concerning use of a real-world space such as an exhibition space.